import java.util.ArrayList;
import java.util.List;

public class BreadthFirstSearch implements Search {
	
	private Graph graph = null;
	private Node node = null;
	private List<Node> visited = new ArrayList<Node>();
	
	public Node solve(String start, String end){
		if(graph != null){
			Node root = graph.getFirstNode(start);
			List<Node> tempList = new ArrayList<Node>();

			tempList.add(root);
			
			while(tempList.size() != 0){
				visited.add(node = tempList.remove(0));
				node.setVisited(true);
				if(node.getContent().equals(end)){
					return graph.getNodeByName(end);
				}
				
				List<Node> children = graph.getNeighbours(node);
				for(Node child : children){
					child.setVisited(true);
					if(visited.indexOf(child) == -1){
						tempList.add(child);
					}
				}
			}
		}
		
		return null;
	}

	public Graph getGraph() {
		return graph;
	}

	public void setGraph(Graph graph) {
		this.graph = graph;
	}

	public List<Node> getVisited() {
		return visited;
	}

	public void setVisited(List<Node> visited) {
		this.visited = visited;
	}

}
